package pers.qianyu.month_202101.date_20210131;

import org.junit.*;

import java.util.*;

/**
 * 第 226 场周赛 第 2 题
 * 5665. 从相邻元素对还原数组
 * https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/
 *
 * @author mizzle rain
 * @date 2021-01-31 14:50
 */
public class RestoreArray {
    // 哈希 + 遍历 （比较笨的做法）
    public int[] restoreArray(int[][] pairs) {
        int len = pairs.length;
        if (len == 0) return new int[0];
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        int[] res = new int[len + 1];
        Map<Integer, Integer> countMap = new HashMap<>();

        for (int[] pair : pairs) {
            Set<Integer> s = map.getOrDefault(pair[0], new HashSet<>());
            s.add(pair[1]);
            map.put(pair[0], s);
            Set<Integer> s2 = map.getOrDefault(pair[1], new HashSet<>());
            s2.add(pair[0]);
            map.put(pair[1], s2);

            countMap.put(pair[0], countMap.getOrDefault(pair[0], 0) + 1);
            countMap.put(pair[1], countMap.getOrDefault(pair[1], 0) + 1);
        }

        int first = 0;
        for (int x : countMap.keySet()) {
            if (countMap.get(x) == 1) {
                first = x;
                break;
            }
        }

        for (int i = 0; i < res.length; i++) {
            if (i == 0) res[i] = first;
            else {
                Set<Integer> set = map.get(res[i - 1]);
                if (set.size() == 1) res[i] = set.iterator().next();
                else {
                    int t = -1;
                    for (int x : set) {
                        if (x != res[i - 2]) {
                            t = x;
                        }
                    }
                    res[i] = t;
                }
            }
        }

        return res;
    }

    @Test
    public void test1() {
        int[] result = new RestoreArray().restoreArray(new int[][]{{2, 1}, {3, 4}, {3, 2}});
        System.out.println("result = " + Arrays.toString(result));
    }

    @Test
    public void test2() {
        int[] result = new RestoreArray().restoreArray(new int[][]{{4, -2}, {1, 4}, {-3, 1}});
        System.out.println("result = " + Arrays.toString(result));
    }

    @Test
    public void test3() {
        int[] result = new RestoreArray().restoreArray(new int[][]{{100000, -100000}});
        System.out.println("result = " + Arrays.toString(result));
    }
}
